package com.gitee.swsk33.algorithms.sort.util;

/**
 * 基本排序算法
 */
public class BasicSort {

	/**
	 * 交换数组中下标为i和j的元素
	 *
	 * @param array 数组
	 * @param i     第一个交换元素索引
	 * @param j     第二个交换元素索引
	 */
	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	/**
	 * 冒泡排序法
	 *
	 * @param array 待排序的数组
	 */
	public static void bubbleSort(int[] array) {
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = 0; j < array.length - i - 1; j++) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j + 1);
				}
			}
		}
	}

	/**
	 * 简单选择排序
	 *
	 * @param array 待排序的数组
	 */
	public static void selectSort(int[] array) {
		int min; // 记录当前元素(i)之后的最小的一个元素的下标
		for (int i = 0; i < array.length; i++) {
			min = i;
			for (int j = i + 1; j < array.length; j++) {
				if (array[j] < array[min]) {
					min = j;
				}
			}
			if (i != min) {
				swap(array, i, min);
			}
		}
	}

	/**
	 * 直接插入排序
	 *
	 * @param array 待排序的数组
	 */
	public static void insertSort(int[] array) {
		int j, temp;
		for (int i = 1; i < array.length; i++) {
			// 若当前位比前一位要小，则将当前位提出赋值给temp然后向前进行插入
			if (array[i] < array[i - 1]) {
				temp = array[i];
				// 把比temp大的元素都往后移
				for (j = i - 1; j >= 0 && temp < array[j]; j--) {
					array[j + 1] = array[j];
				}
				// 此时j指向第一个比temp小的元素，后面的元素已经移动完成，执行插入
				array[j + 1] = temp;
			}
		}
	}

}